/**
 * 合并 K个升序链表
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表
 */
public class exercise04 {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode newNode = new ListNode(-1);
        ListNode cur = newNode;
        if(lists.length == 0) {
            return null;
        }
        while (true){
            int i = 0;
            int count = 0;
            int index = 0;
            ListNode temp = null;
            for(;i<lists.length;i++){
                if(lists[i] == null){
                    count++;
                    continue;
                }
                if(lists[i] != null && temp == null){
                    temp = lists[i];
                    index = i;
                    continue;
                }
                if(lists[i] != null && temp != null && temp.val > lists[i].val){
                    temp = lists[i];
                    index = i;
                }
            }
            // 如果全为空，则返回null
            if(count == lists.length){
                return null;
            }

            lists[index] = lists[index].next;
            cur.next = temp;
            cur = cur.next;
            if(count == lists.length - 1){
                break;
            }
        }
        return newNode.next;
    }
}
